package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 我怎么感觉是回溯和滑动窗口呢？
 *
 * 找一个队列记录当前的所有节点
 * 一个值记录总和
 * 一个全局的个数
 *
 * 相等就个数加一，队列往下挪一个，
 *
 * 算了看答案吧，感觉不是很可行
 *
 * */
public class _437_path_sum {
    
    /*
    * dfs
    *
    * */
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        int res = rootSum(root, targetSum);
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        return res;
    }
    /*
    * target 得是 long ，不然可能溢出，导致结果错乱
    * */
    int rootSum (TreeNode root, long target) {
        if (root == null) return 0;
        int res = 0;
        if (root.val == target) res = 1;
        res += rootSum(root.left, target - root.val);
        res += rootSum(root.right, target - root.val);
        return res;
    }
    
    /*
     * dp
     *
     * 不知道这个叫不叫 dp，是用的前缀和：
     * 有个参数叫 cur，记录当前的总和
     * 一个 map，记录长度为 key 的有 value 个
     * 每到一个节点，记录 cur - targetSum 是不是在 map 里
     * 访问完这个节点，要清除它的信息
     *
     * 长度为 0 的有一种情况得记下来，这是边界
     *
     * */
    Map<Long, Integer> map = new HashMap<>();
    public int pathSum2(TreeNode root, int targetSum) {
        map.put(0L, 1);
        return dfs(root, 0, targetSum);
    }
    int dfs(TreeNode root, long cur, int target) {
        if (root == null) return 0;
        cur += root.val;
        int res = map.getOrDefault(cur - target, 0);
        map.put(cur, map.getOrDefault(cur,0) + 1);
        res += dfs(root.left, cur, target);
        res += dfs(root.right, cur, target);
        map.put(cur, map.get(cur) - 1);
        return res;
    }
}
